#include <bits/stdc++.h>

using namespace std;


/*
3443. K 次修改后的最大曼哈顿距离
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

'N'：向北移动 1 个单位。
'S'：向南移动 1 个单位。
'E'：向东移动 1 个单位。
'W'：向西移动 1 个单位。
初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

 

示例 1：

输入：s = "NWSE", k = 1

输出：3

解释：

将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。

移动操作	位置 (x, y)	曼哈顿距离	最大值
s[0] == 'N'	(0, 1)	0 + 1 = 1	1
s[1] == 'W'	(-1, 1)	1 + 1 = 2	2
s[2] == 'N'	(-1, 2)	1 + 2 = 3	3
s[3] == 'E'	(0, 2)	0 + 2 = 2	3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3

输出：6

解释：

将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。

执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

 

提示：

1 <= s.length <= 105
0 <= k <= s.length
s 仅由 'N'、'S'、'E' 和 'W' 。
*/


// 法一
class Solution {
public:
    int maxDistance(string s, int k) {
        int ans = 0; // 初始化最大曼哈顿距离为0
        int north = 0, south = 0, east = 0, west = 0; // 分别记录四个方向的移动次数

        // 遍历字符串中的每个字符
        for (char it : s) {
            // 根据字符更新对应方向的计数
            switch (it) {
            case 'N':
                north++; // 北方向移动次数加1
                break;
            case 'S':
                south++; // 南方向移动次数加1
                break;
            case 'E':
                east++;  // 东方向移动次数加1
                break;
            case 'W':
                west++;  // 西方向移动次数加1
                break;
            }

            // 计算可以修改的N/S方向的次数，不超过k次
            int times1 = min({north, south, k});        // N和S方向的修改次数
            // 计算可以修改的E/W方向的次数，不超过剩余修改次数（k - times1）
            int times2 = min({east, west, k - times1}); // E和W方向的修改次数

            // 更新最大曼哈顿距离
            ans = max(ans,
                      count(north, south, times1) + count(east, west, times2));
        }
        return ans; // 返回最大曼哈顿距离
    }

    // 计算修改后的曼哈顿距离
    int count(int drt1, int drt2, int times) {
        // 公式：|drt1 - drt2| + 2 * times
        // 其中，times是修改次数，每次修改可以增加2个单位距离
        return abs(drt1 - drt2) + times * 2;
    }
};

// 法二
class Solution {
public:
    int maxDistance(string s, int k) {
        int rnt = 0; // 初始化最大曼哈顿距离为0
        vector<int> v(2); // v[0]记录南北方向位移，v[1]记录东西方向位移

        // 遍历字符串中的每个字符
        for(int i = 0; i < s.size(); i++){
            // 根据字符更新位移向量
            if(s[i] == 'N') v[0]++;       // 北方向：y坐标+1
            else if(s[i] == 'S') v[0]--;  // 南方向：y坐标-1
            else if(s[i] == 'E') v[1]++;  // 东方向：x坐标+1
            else v[1]--;                  // 西方向：x坐标-1

            // 计算当前可能的最大曼哈顿距离：
            // 1. 实际位移的曼哈顿距离：abs(v[0]) + abs(v[1])
            // 2. 加上k次修改能带来的最大增益：k*2（每次修改最多增加2单位距离）
            // 3. 但最大距离不能超过当前步数i+1（因为每步最多移动1单位）
            rnt = max(rnt, min(abs(v[0]) + abs(v[1]) + k * 2, i + 1));
        }
        return rnt; // 返回最大曼哈顿距离
    }
};